qiaoshun8888 / Algorithm

The binary tree node class ::

class Node(object):

    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
        self.parent = None

So one node instance should has its value, left node, right node, parent node. Except value is required, the others by default are None.

Use BFS as its iterator::

def __iter__(self):
    stack = []
    stack.append(self)
    while stack:
        node = stack.pop(0)
        yield node
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

BFS needs a queue, which we use list as an alternative. list.append append the value to the end of the list. list.pop(0) always pop out the first element of the list. However I think pop(0) is O(n) time complexity.

zhouxin created at 10 years, 8 months ago